class Zcsh {

    private int[][] cacheMatrix;

    public NumMatrix(int[][] matrix) {
        if (matrix.length != 0 && matrix[0].length != 0) {
            cacheMatrix = new int[matrix.length + 1][matrix[0].length + 1];
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    if (i == 0) {
                        cacheMatrix[i + 1][j + 1] = matrix[i][j] + cacheMatrix[1][j];
                    } else if (j == 0) {
                        cacheMatrix[i + 1][j + 1] = matrix[i][j] + cacheMatrix[i][1];
                    } else {
                        cacheMatrix[i + 1][j + 1] = cacheMatrix[i + 1][j] + cacheMatrix[i][j + 1] - cacheMatrix[i][j] + matrix[i][j];
                    }
                }
            }
        }

    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int up = cacheMatrix[row2 + 1][col1];
        int left = cacheMatrix[row1][col2 + 1];
        int upLeft = cacheMatrix[row1][col1];
        return cacheMatrix[row2 + 1][col2 + 1] - up - left + upLeft;
    }
}